Compilers may be used to translate a program that is written in a first programming language to an equivalent program that conforms to a second programming language different than the first programming language. The program code that is written in the first programming language may be referred to as source code, and the program code that is written in the second programming language may be referred to as target code.
Oftentimes, the source code for a compiler is written in a high-level programming language and the compiler translates the high-level source code into a target code that corresponds to a low-level programming language, such as, e.g., assembly language code or object code. In such examples, the high-level programming language may not specify how the program variables are stored in the physical registers of the underlying processor that will run the program. On the other hand, the low-level programming language may specify particular physical registers that will store the program variables at any given time in the program. In other words, the high-level programming language may be a register-independent programming language while the low-level programming language may be a register-specific programming language.
In order to translate source code that is written in a register-independent programming language to a register-specific programming language, a compiler may perform register allocation. Register allocation may refer to the process of assigning physical registers to variables and/or temporaries of the program that is being compiled. The variables of the program may correspond to variables that are specified in the source code for the program. The temporaries of the program may refer to temporary variables that are generated by a compiler while compiling the program.
The number of physical registers in a processor is generally limited, and for many types of programs, the number of variables and temporaries may outnumber the number of physical registers available to store such variables and temporaries. In such cases, some of the variables and/or temporaries that are stored in the physical registers may need to be transferred to external memory to accommodate other variables and/or temporaries that also need to use the physical registers.
Transferring variables and/or temporaries that are stored in registers to external memory to accommodate other variables and/or temporaries may be referred to as spilling the registers into memory. Spilling registers may reduce the performance of a program because of memory access latencies associated with transferring the register values to and from memory. Designing register allocators to reduce spilling and produce efficient compiled code with a limited number of physical registers presents a significant challenge to compiler programmers.